package leetcode.tree_problem;

import java.util.*;

/**
 * 102. 二叉树的层序遍历
 * https://leetcode-cn.com/problems/binary-tree-level-order-traversal/
 */
public class LevelOrder {
    public List<List<Integer>> levelOrder(TreeNode root) {
        //用来存放所有的树节点
        List<List<Integer>> treeNodeList = new ArrayList<>();
        //边界判断
        if (root == null)
            return treeNodeList;
        //定义存放下一层所有元素的队列
        Deque<TreeNode> deque = new LinkedList<>();
        //先把树根入队
        deque.offer(root);
        //队列判处条件
        while (!deque.isEmpty()){
            //定义存放前一层的列表
            List<Integer> list = new ArrayList<>();
            int size = deque.size();//这一步很妙队列size会变化所以必须放在循环外面因为dequeue在while外面长度不变所以在里面要重新定义长度
            for (int i = 0; i < size; i++) {
                //把队首出队记录
                TreeNode cur = deque.poll();
                //把值放进cur的列表
                list.add(cur.val);
                //如果该树节点cur的左右节点不为空则把左右节点入队
                if (cur.left != null){
                    deque.offer(cur.left);
                }
                if (cur.right != null){
                    deque.offer(cur.right);
                }

            }
            //for循环走完说明当前层已经加入list且出队，下一层元素以入队
            treeNodeList.add(list);
        }
        //while走完说明list加完了；把list放进treeNodeList
        return treeNodeList;
    }
}
